编译原理：中间代码IR

IR,中间代码(Intermediate Representation,有时也称为Intermediate Code,IC)，它是编译器中很重要的一种数据结构。编译器在做完前端工作以后，首先就生成IR,并在此基础上执行各种优化算法，最后再生成目标代码。

设计IR的目的， 是要满足编译器中的各种需求。

需求的不同，就会导致IR的设计不同

通常情况下，IR有两种用途，一种是用来做分析和变换的，一种是直接用于解释执行的。

基于这种从高到底的抽象层，IR可以归结为HIR/MIR和LIR三类

假设你要开发一款 IDE，那最主要的功能包括：发现语法错误、分析符号之间的依赖关系（以便进行跳转、判断方法的重载等）、根据需要自动生成或修改一些代码（提供重构能力）。

这个时候，你对 IR 的需求，是能够准确表达源语言的语义就行了。这种类型的 IR，可以叫做 High IR，简称 HIR。

其实，AST 和符号表就可以满足这个需求。也就是说，AST 也可以算作一种 IR。 如果你要开发 IDE、代码翻译工具（从一门语言翻译到另一门语言）、代码生成工具、代码统计工具等，使用 AST（加上符号表）就够了。

基于HIR,可以做一些高层次的代码优化，比如常数折叠/内联等。在Java和Go的编译器中，可以看到不少基于AST做的优化工作。

大量的优化算法是可以通用的，没有必要依赖源语言的语法和语义，也没有必要依赖具体的 CPU 架构。

这些优化包括部分算术优化、常量和变量传播、死代码删除等，实现这些类分析和优化功能的IR可以叫做Middle IR,简称MIR.

因为MIR跟源代码和目标代码都无关，所以在讲解优化算法时，通常是基于MIR,比如三地址代码(Three Address Code,TAC).

TAC的特点是：最多三个地址(也就是变量)，其中赋值符号的左边是用来写入的，而右边最多可以有两个地址和一个操作符，用于读取数据并计算。

举例： 示例函数foo:

对应的TAC可能是：

可以看到，TAC 用 goto 语句取代了 if 语句、循环语句这种比较高级的语句，当然也不会有类、继承这些高层的语言结构。但是，它又没有涉及数据如何在内存读写等细节，书写格式也不像汇编代码，与具体的目标代码也是独立的。

所以，它的抽象程度算是不高不低。

最后一类IR就是Low IR,简称LIR

这类IR的特点，是它的指令通常可以与机器指令一一对应，比较容易翻译成机器指令(或汇编代码)。因为LIR体现了CPU架构的底层特征，因此可以做一些于具体CPU架构相关的优化。

比如，下面是 Java 的 JIT 编译器输出的 LIR 信息，里面的指令名称已经跟汇编代码很像了，并且会直接使用 AMD64 架构的寄存器名称。 Java的JIT编译器的LIR：

编译过程可以理解为，抽象层次高的 IR 一直 lower 到抽象层次低的 IR 的过程，并且在每种 IR 上都会做一些适合这种 IR 的分析和处理工作，直到最后生成了优化的目标代码。

扩展：lower 这个词的意思，就是把对计算机程序的表示，从抽象层次比较高的、便于人理解的格式，转化为抽象层次比较低的、便于机器理解的格式。

注：P-code也可能被进一步编译，形成可以直接执行的机器码 Java 的字节码就是这样的例子。因此，在本节中探究 Java 的两个编译器，一个把源代码编译成字节码，一个把字节码编译成目标代码（支持 JIT 和 AOT 两种方式）。

IR通常是没有书写格式的

在少量情况下，IR 有比较严格的输出格式，不仅用于显示和分析，还可以作为结果保存，并可以重新读入编译器中。比如，LLVM 的 bitcode，可以保存成文本和二进制两种格式，这两种格式间还可以相互转换

以 C 语言为例，来看下 fun1 函数，及其对应的 LLVM IR 的文本格式和二进制格式：

LLVM IR 的文本格式("clang -emit-llvm -S fun1.c -o fun1.ll"命令生成，这里只节选了主要部分)：

二进制格式(用"clang -emit-llvm -c fun1.c -o fun1.bc"命令生成，用"hexdump -C fun1.bc"命令显示)： LLVM IR的二进制格式：

在实际的实现中，有线性结构/树结构/有向无环图(DAG)/程序依赖图(PDG)等多种格式。编译器会根据需要，选择合适的数据结构。

在运行某些算法的时候，采用某个数据结构可能会更顺畅，而采用另一些结构可能会带来内在的阻滞。所以，一定要根据具体要处理的工作特点，来选择合适的数据结构。

下面来看下各种格式的特点。

可以把代码表示成一行行的指令或语句，用数组或者列表保存就行了。其中的符号，需要引用符号表，来提供类型等信息。

这种线性结构有时候也被称作 goto 格式。因为高级语言里的条件语句、循环语句，要变成用 goto 语句跳转的方式。

树结构也可以用作IR,AST就是一种树结构。

树结构的缺点是：可能有冗余的子树。 比如，语句"a=5; b=(2+a)+a*3;"形成的AST就有冗余。如果基于这个树结构生成代码，可能会做两次从内存中读取 a 的值的操作，并存到两个临时变量中。 冗余的子树：

DAG 结构，是在树结构的基础上，消除了冗余的子树。比如，上面的例子转化成 DAG 以后，对 a 的内存访问只做一次就行了。 GAG结构消除了冗余的子树： 在 LLVM 的目标代码生成环节，就使用了 DAG 来表示基本块内的代码。

程序依赖图，是显式地把程序中的数据依赖和控制依赖表示出来，形成一个图状的数据结构。基于这个数据结构，我们再做一些优化算法的时候，会更容易实现。

这种数据结构里，因为会有很多图节点，又被形象地称为“节点之海（Sea of Nodes）”

接下来介绍一个重要的IR设计范式：SSA格式

SSA 是** Static Single Assignment ** 的缩写，也就是静态单赋值。 这是 IR 的一种设计范式，它要求一个变量只能被赋值一次。我们来看个例子。

“y = x1 + x2 + x3 + x4”的普通 TAC 如下：

其中，y被赋值三次，如果写成SSA的形式，就只能写成下面的样子：

那为什么要费力写成这种形式呢，还要为此多添加t1和t2两个临时变量？

原因是，使用SSA的形式，体现了精确的使用--定义(use-def)关系，并且由于变量的值定义出来后就不再变化，使得基于SSA更容易运行一些优化算法。

在SSA格式的IR中，有些特别的指令，叫做phi指令，举个例子： 同样对于示例代码：

它对应SSA格式的IR可以写成：

其中，变量b有四个版本：b1是初始值，b2是else块(BB2)的取值，b3是if块(BB3)的取值，最后一个基本块(BB4)要把b的最后取值作为函数返回值。很明显，b的取值有可能是b2,也有可能是b3,这个时候，就需要phi指令了。

phi指令，会根据控制流的实际情况确定b4的值。 如果BB4的前序节点是BB2,那么b4的取值是b2；而如果BB4的前序节点是BB3,那么b4的取值就是b3.所以，如果要满足SSA的要求，也就是一个变量只能赋值一次，那么在遇到程序分支的情况下，就必须引入phi指令。

最后要指出的是：由于SSA格式的有点，现代语言用于优化的IR,很多都是基于SSA的了，包括Java的JIT编译器/JavaScript的V8编译器/Go语言的gc编译器/Julia编译器以及LLVM工具等。 所以一定要高度重视SSA.

IR的几个重要概念：

根据抽象层次和使用目的的不同，可以设计不同的IR.

IR可能采取多种数据结构，每种结构适合不同的处理工作

由于SSA格式的有点，主流的编译器都在采用这种范式来设计IR

参考： 中间代码：不是只有一副面孔